#include <cstdio>
#include <algorithm>
using namespace std;
//#define MAXV 1000
const int MAXV = 1000;
const int INF = 100000000;
int n, G[MAXV][MAXV];       //n为顶点数
int d[MAXV];                //记录源节点距对应节点的最短路径距离
bool visit[MAXV] = {false}; //访问标记
void Dijkstra(int s)        //s为源点
{//O(V^2)
    //初始化
    fill(d, d + MAXV, INF); //fill()函数将整个d数组赋值为INF
    d[s] = 0;
    int min, m;
    for (int i = 0; i < n; ++i)
    { //循环n次，求解最短路径
        min = INF; m = -1;
        //二级循环，循环n次，找到距源点最短且未被访问的结点，访问之，同时以此结点为中介更新距离数组d[]
        for (int j = 0; j < n; ++j)
        {
            if (d[j] < min && false == visit[j])
            {
                min = d[j];
                m = j;
            }
        }
        if(-1 == m)
        {//找不到小于距离INF的结点，说明剩下的结点与源点并不连通
            return;
        }
        visit[m] = true;
        for (int j = 0; j < n; ++j)
        {
            if (false == visit[j] && G[m][j] != INF && d[m] + G[m][j] < d[j])
            {//前两个判断可以防止数据过大时导致的溢出
                d[j] = d[m] + G[m][j];
            }
        }
    }
    return;
}
int main()
{
}